package com.likeycy.my.singly;

import com.likeycy.my.AbstractList;
import com.likeycy.my.List;

/**
 * @ClassName: MySinglyLinkedList
 * @Description: 实现自己的单向链表
 * @Author: sodagreen
 * @Date: 2021/2/23 2:54
 * @Version: 1.0
 */
public class MySinglyLinkedList<E> extends AbstractList<E> implements List<E> {

    /** 头节点 */
    private Node<E> first;

    /**
     * 存放数据且指向后继节点的实体
     *
     * @param <E>
     */
    private static class Node<E> {
        /**
         * 存放的要添加的元素数据
         */
        E element;
        /**
         * 下一个节点
         */
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }

        @Override
        protected void finalize() throws Throwable {
            System.out.println("LinkedList——Node<E>——finalize()，内存回收了");
        }
    }

    @Override
    public E get(int index) {
        // 现在我们有了根据index位置返回该index位置的Node节点的公共方法。所以我们直接调用即可
        return indexByCurrentNode(index).element;
    }

    @Override
    public E set(int index, E element) {
        // 先获取指定索引位置的Node节点
        Node<E> node = indexByCurrentNode(index);
        // 保存查找到的node里的element数据，然后再替换为新的数据
        E oldElementValue = node.element;
        node.element = element;
        return oldElementValue;
    }

    /**
     * 往指定索引位置添加元素
     * @param index 要添加到集合中的指定索引位置
     * @param element 要添加到集合中指定索引位置的元素
     */
    @Override
    public void add(int index, E element) {
        /*
          插入需要注意的问题：
          由于我们设计的是单向链表，一个节点只知道下一个节点在哪里，不知道上一个节点在哪里。我们可以根据index找到在该index位置上的Node节点，
          新增的节点的时候，我们只要把新节点的next属性指向查找到的Node节点即可。但是我们怎么让上一个节点指向新增的这个节点呢？
          解决办法也简单，那就是查找时，不查找index位置上的Node节点对象，而是查找（index-1）位置上的Node节点对象。因为 (index-1)位置上的
          Node节点中的next属性指向的就是我们要找的index位置上的Node节点对象。如果是在双向链表中，就不会有这个问题了。
          听起来很绕，就像找人一样，找自己，只能找到自己和自己的孩子。但是找爸爸，却可以找到爸爸和自己。
          以上只是解决了一个问题。还存在一个问题，那就是如果索引值为0，我们按照(index-1)方式查找，那不就报错了吗？原本的正常操作，现在却变成
          异常操作了。这个问题解决办法也简单，在添加前先判断要添加的元素位置是不是头节点位置。如果是，直接创建一个新的Node节点，并将节点的next
          属性指向first。此时新的节点成为了名义上的first节点。然后将新的节点赋值给first成员变量。这样新的节点才是实际上的first节点。
         */
        rangeCheckForAdd(index);
        if (index == 0) {
            first = new Node<>(element, first);
        } else {
            // 获取到index前一个位置的节点
            Node<E> prev = indexByCurrentNode(index - 1);
            // 将前一个位置的节点指向新增的节点，同时新增的节点指向index位置上的Node节点
            prev.next = new Node<>(element, prev.next);
        }
        size++;
    }

    @Override
    public E remove(int index) {
        /*
          删除其实遇到的和新增是一样的问题。即单向链表里，删除指定index位置上的Node节点后，被删除Node节点的前一个节点，和后一个节点要怎么关
          联起来行程一串。毕竟每个节点只记得下一个节点不记得上一个节点。直接删除，那相当于是把指定index位置上的Node节点和其后面的所有节点都被
          删除了。所以还是得根据 (index-1) 找到要删除节点的前一个节点来操作。
          另外如果index传的是0，那么处理又该是另外一种情况了。
         */
        rangeCheck(index);
        Node<E> node = first;
        if (0 == index) {
            first = first.next;
        } else {
            Node<E> prev = indexByCurrentNode(index - 1);
            // 获得当前指定index位置上的Node对象
            node = prev.next;
            // 将前一个节点指向被删除节点的后面一个节点，重新形成链表
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        /*
          根据指定元素查找该元素在链表中的位置时，有几个方面要考虑。
          1. 传的元素为 null 时怎么处理？因为如果用equals比较时，null会报空指针异常。
           答1：如果为 null,先判断传的元素是不是为 null，遍历的时候，用 == 符号判断。而不是equals。就像问题说的，用equals会报空指针
          2. 传的元素为 Object类型时，也用 == 比较吗？
           答2：传的类型为 Object类型时，应该用equals方法比较。 ==符号比较的只是内存地址值而已。每个 Object 对象在内存中的地址值都不一样。
               如果用 == 符号，那将永远找不到，即使链表里面有该元素。
          3. 指定的元素在该链表中有多个重复的，该返回哪个索引？
           答3：有多个重复元素的时候，直接返回第一个和该元素相同元素所在位置的索引。
          4. 链表中没有该元素返回什么？
           答4：返回 -1。这属于开发者的约定，-1就表示链表中不包含该元素。
         */
        Node<E> node = first;
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (null == node.element) {
                    return i;
                }
                node = node.next;
            }
        } else {
            int i = 0;
            // 这里用两种循环方式遍历仅供参考
            while (null != node) {
                if (element.equals(node.element)) {
                    return i;
                }
                node = node.next;
                i++;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 清空链表集合
     */
    @Override
    public void clear() {
        /*
          链表集合和动态数组不同的地方在于，清空了集合长度，是不会释放Node节点的。每一个Node在内存中都是一个对象，都有一份地址值。
          清空了总长度，在栈空间内依然有变量指向着所属的Node节点。这个变量名称就是 first。我们都知道，因为first还指向下一个节点。
          JVM的垃圾回收期就会认为该一片链表集合依然有引用在持有者，不会被清理释放内存。所以我们需要显示的释放内存，断掉节点之间的引用。
          也就是置为 null
         */
        size = 0;
        first = null;
    }

    /**
     * 根据指定的索引位置返回链表集合中当前位置上的Node节点对象
     *
     * @param index
     * @return
     */
    private Node<E> indexByCurrentNode(int index) {
        // 首先需要检查索引是否越界
        rangeCheck(index);
        /*
          现在需要查找指定index位置的Node节点，那么肯定需要循环遍历。链表的遍历总是从首节点开始的，就像打造一条锁链，总是现有第一个，然后第二
          个串到第一个上，进行链接。也就是说，遍历肯定是从 first 节点开始。如何找到下一个节点呢？那就是 first节点的 next 属性指向的就是指向
          的下一个节点，下一个节点的 next 属性又指向了下一个节点，以此类推……
         */
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size=").append(size);
        sb.append(", ").append(this.getClass().getSimpleName()).append(", [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (i != 0) {
                sb.append(", ");
            }
            sb.append(node.element);
            node = node.next;
        }
        sb.append(']');
        return sb.toString();
    }
}
